|
right A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities) where the priority is changing as a continuous function of time. As a type of kinetic priority queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property - if is a child node of , then the priority of the element in must be higher than the priority of the element in . This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue (the event queue) to maintain certificate failure times. == Implementation and operations == A regular heap can be kinetized by augmenting with a certificate [] for every pair of nodes, such that is a child node of . If the value stored at a node is a function of time, then this certificate is only valid while . Thus, the failure of this certificate must be scheduled in the event queue at a time such that . All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kinetic heap」の詳細全文を読む スポンサード リンク
|
